#include <iostream>
using namespace std;
namespace hcc
{
    //搜索二叉树的节点
    template<class K>
    struct BSTnode 
    {
        K _val;
        BSTnode<K>* _left;
        BSTnode<K>* _right; 
        explicit BSTnode(const K& x=K())
            : _val(x)
            , _left(nullptr)
            , _right(nullptr)
        {}
    };
    //搜索二叉树
    template<class K>
    class BST
    {
        public:
        typedef BSTnode<K> BSTNode;
        BST()
            : _root(nullptr)
        {}
        //拷贝构造函数
        BST(const BST<K>& d)
            : _root(nullptr)
        {
            copy(d);
        }
        BST<K>& operator=(BST<K> d)
        {
            std::swap(_root,d._root);
            return *this;
        }
        void copy(const BST<K>& d)
        {
            _root=_copy(d._root);
        }
        BSTNode* _copy(const BSTNode* root)
        {
            if(root==nullptr)
                return nullptr;
            BSTNode* cur=new BSTNode(root->_val);
            cur->_left=_copy(root->_left);
            cur->_right=_copy(root->_right);
            return cur;
        }
        //插入(创建)
        bool insert(const K& x)
        {
            if(_root==nullptr)
            {
                _root=new BSTNode(x);
                return true;
            }
            BSTNode* parent=nullptr;
            BSTNode* cur=_root;
            while(cur)
            {
                if(x<cur->_val)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(x>cur->_val)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else
                    return false;
            }
            cur=new BSTNode(x);
            if(parent->_val>x)
            {
                parent->_left=cur;
                return true;
            }
            else
            {
                parent->_right=cur;
                return true;
            }
        }
        bool find(const K& x)
        {
            if(_root==nullptr)
                return false;
            BSTNode* cur=_root;
            while(cur)
            {
                if(cur->_val>x)
                    cur=cur->_left;
                else if(cur->_val<x)
                    cur=cur->_right;
                else
                    return true;
            }        
            return false;
        }
        bool earse(const K& x)
        {
            if(_root==nullptr)
                return false;
            BSTNode* parent=nullptr;
            BSTNode* cur=_root;
            BSTNode* del=nullptr;
            while(cur)
            {
                if(cur->_val<x)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else if(cur->_val>x)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else
                {
                    //单分支节点(包含叶子结点情况)
                    if(cur->_left==nullptr)
                    {
                        if(_root==cur)
                        {
                            del=_root;
                            _root=cur->_right;
                            delete del;
                            del=nullptr;
                            return true;
                        }
                        else
                        {
                            if(parent->_val>cur->_val)
                            {
                                del=cur;
                                parent->_left=cur->_right;
                                delete del;
                                del=nullptr;
                                return true;
                            }
                            else
                            {
                                del=cur;
                                parent->_right=cur->_right;
                                delete del;
                                del=nullptr;
                                return true;
                            }
                        }
                    }
                    else if(cur->_right==nullptr)
                    {
                        if(cur==_root)
                        {
                            del=cur;
                            _root=cur->_left;
                            delete del;
                            del=nullptr;
                            return true;
                        }
                        else
                        {
                            if(parent->_val<cur->_val)
                            {
                                del=cur;
                                parent->_right=cur->_left;
                                delete del;
                                del=nullptr;
                                return true;
                            }
                            else
                            {
                                del=cur;
                                parent->_left=cur->_left;
                                delete del;
                                del=nullptr;
                                return true;
                            }
                        }
                    }
                    //双分支节点情况(找后继结点来替换)
                    BSTNode* minparent=cur;
                    BSTNode* min=cur->_right;
                    while(min->_left)
                    {
                        minparent=min;
                        min=min->_left;
                    }
                    if(cur->_right==min)
                    {
                        std::swap(cur->_val,min->_val);
                        del=min;
                        minparent->_right=min->_right;
                        delete del;
                        del=nullptr;
                        return true;
                    }
                    else
                    {
                        std::swap(min->_val,cur->_val);
                        del=min;
                        if(minparent->_val>min->_val)
                        {
                            minparent->_left=min->_right;
                            delete del;
                            del=nullptr;
                            return true;
                        }
                        else
                        {
                            minparent->_right=min->_right;
                            delete del;
                            del=nullptr;
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        void print()
        {
            printmid(_root);
            cout<<endl;
        }
        size_t sizenode(BSTNode* root)
        {
            if(root==nullptr)
                return 0;
            size_t left=sizenode(root->_left);
            size_t right=sizenode(root->_right);
            return left+right+1;
        }
        size_t high(BSTNode* root)
        {
            if(root==nullptr)
                return 0;
            size_t left=high(root->_left);
            size_t right=high(root->_right);
            if(left<right)
                return right+1;
            else
                return left+1;
        }
        bool swap(BSTNode* root)
        {
            if(root==nullptr)
                return false;
            std::swap(root->_left,root->_right);
            bool left=swap(root->_left);
            bool right=swap(root->_right);
            return left&&right;
        }
        private:
        void printmid(BSTNode* root)
        {
            if(root==nullptr)
                return;
            printmid(root->_left);
            cout<<root->_val<<"->";
            printmid(root->_right);
        }
        BSTNode* _root;
    };
}
